package source.dynamic;

import org.junit.Test;

import java.math.BigInteger;
import java.util.*;

public class Interleave {
    public boolean isInterleave(String s1, String s2, String s3) {
        int n = s1.length(), m = s2.length(), t = s3.length();
        // 基础检查：如果长度不匹配，s3 不可能由 s1 和 s2 交错组成
        if (n + m != t) {
            return false;
        }
        // 创建动态规划数组，f[j] 表示（在固定s1的某个前缀长度下）s2的前j个字符是否能参与组成s3的前缀
        boolean[] f = new boolean[m + 1];
        // 初始化：两个空字符串可以交错组成一个空字符串
        f[0] = true;
        // 外层循环：i 可视为当前考虑 s1 的前 i 个字符 (从0到n)
        for (int i = 0; i <= n; ++i) {
            // 内层循环：j 可视为当前考虑 s2 的前 j 个字符 (从0到m)
            for (int j = 0; j <= m; ++j) {
                int p = i + j - 1; // p 是当前在 s3 中要匹配的字符索引（从0开始）
                // 情况1：考虑当前字符可能来自 s1（前提是 i > 0，即s1有字符可用）
                if (i > 0) {
                    // 状态转移：f[j] 的当前值（基于上一轮i的结果）代表不考虑s1第i个字符时的状态。
                    // 现在需要检查：
                    // 1. 之前的状态f[j]是否为true（即s1的前i-1位和s2的前j位能组成s3的前i+j-1位）；
                    // 2. s1的第i个字符（即s1.charAt(i-1)）是否等于s3的第p+1个字符（即s3.charAt(p)）。
                    // 只有两者都满足，才能说明当前路径可行。
                    f[j] = f[j] && s1.charAt(i - 1) == s3.charAt(p);
                }
                // 情况2：考虑当前字符可能来自 s2（前提是 j > 0，即s2有字符可用）
                if (j > 0) {
                    // 状态转移：f[j-1] 代表不考虑s2第j个字符时的状态。
                    // 需要检查：
                    // 1. 之前的状态f[j-1]是否为true（即s1的前i位和s2的前j-1位能组成s3的前i+j-1位）；
                    // 2. s2的第j个字符（即s2.charAt(j-1)）是否等于s3的第p+1个字符（即s3.charAt(p)）。
                    // 使用 || 是因为只要来自s1或s2的任意一条路径可行，当前状态f[j]就为true。
                    f[j] = f[j] || (f[j - 1] && s2.charAt(j - 1) == s3.charAt(p));
                }

            }
        }
        // 最终结果：f[m] 表示 s1 的全部 n 个字符和 s2 的全部 m 个字符是否能交错组成 s3 的全部 (n+m) 个字符。
        return f[m];
    }

    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<int[]> heap = new PriorityQueue<>((o1, o2) -> {
            return o1[0] + o1[1] - o2[0] - o2[1];
        });
        int m = nums1.length, n = nums2.length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                heap.add(new int[]{nums1[i], nums2[j]});
            }
        }

        List<List<Integer>> lists = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            int[] list = heap.poll();
            assert list != null;
            lists.add(List.of(list[0], list[1]));
        }

        return lists;
    }

    /**
     * 打家劫舍
     *
     * @param nums int[]
     * @return int
     */
    public int rob(int[] nums) {
        // 处理边界情况：如果房屋数组为空或长度为0，直接返回0。
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int length = nums.length;
        // 如果只有一间房屋，那么最大金额就是这间房屋的金额。
        if (length == 1) {
            return nums[0];
        }

        // 初始化动态规划的前两个状态
        // first 代表偷窃到前前个房屋（即i-2）时的最大金额
        int first = nums[0];
        // second 代表偷窃到前一个房屋（即i-1）时的最大金额
        // 对于前两间房屋，最大金额是两间房中金额较大的那一间。
        int second = Math.max(nums[0], nums[1]);

        // 从第三间房屋（索引为2）开始遍历
        for (int i = 2; i < length; i++) {
            // 临时保存second的当前值，这个值在下一次循环中将成为first（即i-1）
            int temp = second;
            // 计算偷窃到当前房屋i时的最大金额：
            // 选择1: 偷当前房屋 -> first + nums[i] （因为不能偷相邻的i-1）
            // 选择2: 不偷当前房屋 -> second （金额与到i-1时相同）
            // 取两者中的最大值作为新的second（即偷窃到当前房屋i的最大金额）
            second = Math.max(first + nums[i], second);
            // 更新first，为下一次循环做准备。将first移动至当前second的前一个状态（即旧的second）
            first = temp;
        }
        // 循环结束后，second存储的就是偷窃到最后一间房屋时的最大金额。
        return second;
    }


    /**
     * 单词拆分
     *
     * @param s        判断是否可拆分字符串
     * @param wordDict 字符串字典
     * @return 是否可拆分
     */
    public boolean wordBreak(String s, List<String> wordDict) {
        int len = s.length();
        boolean[] dp = new boolean[len + 1];
        dp[0] = true;
        for (int i = 0; i <= len; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordDict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[len];
    }

    @Test
    public void test() {
        List<List<Integer>> ans = new ArrayList<>();
        ans.add(new ArrayList<>(List.of(1, 2)));

        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));

        pq.offer(new int[]{1, 2});
        pq.offer(new int[]{12, 12});
        pq.offer(new int[]{11, 2});
        pq.offer(new int[]{110, 2});
        pq.offer(new int[]{101, 2});
        pq.offer(new int[]{310, 2});
        pq.offer(new int[]{21, 2});

        System.out.println(Arrays.toString(pq.poll()));
        System.out.println(Arrays.toString(pq.poll()));

        PriorityQueue<Integer> queue = new PriorityQueue<>();
        queue.add(12);
        queue.add(12);
        queue.add(12);
        queue.add(1);

        System.out.println(queue.poll());

        int[] nums1 = new int[0];
        int[] nums2 = new int[0];
        int k = 0;
        PriorityQueue<int[]> pheap = new PriorityQueue<>((o1, o2) -> nums1[o1[0]] + nums2[o1[1]] - nums1[o2[0]] - nums2[o2[1]]);


    }

    @Test
    public void testN() {
        int n = 100;
        BigInteger ans = new BigInteger("1");

        for (int i = 2; i <= n; i++) {
            ans = ans.multiply(BigInteger.valueOf(i));
        }
        System.out.println(ans);
    }

    public int trailingZeroes(int n) {
        int k = 0;
        int N = n;
        for (int i = 1; i <= N; i++) {
            n = i;
            while (n > 0) {
                if (n % 5 == 0) {
                    k++;
                    n /= 5;
                } else break;
            }
        }
        return k;
    }

    @Test
    public void testN2() {
        System.out.println(trailingZeroes(20));

        ArrayList<Integer> list = new ArrayList<>();
        list.add(11);
        list.add(21);
        list.sort((i1,i2)->i2-i1);


        System.out.println(list.get(0));

//        list.remove(1);
    }

}
